<html>
  <head>
    <meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>K-means算法 | JIANG-HS</title>
<link rel="shortcut icon" href="https://JIANG-HS.github.io/favicon.ico?v=1600693149942">
<link href="https://cdn.jsdelivr.net/npm/remixicon@2.3.0/fonts/remixicon.css" rel="stylesheet">
<link rel="stylesheet" href="https://JIANG-HS.github.io/styles/main.css">
<link rel="alternate" type="application/atom+xml" title="K-means算法 | JIANG-HS - Atom Feed" href="https://JIANG-HS.github.io/atom.xml">
<link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Droid+Serif:400,700">


<script async src="https://www.googletagmanager.com/gtag/js?id=UA-xxxxxxxxx-x"></script>
<script>
  window.dataLayer = window.dataLayer || [];
  function gtag(){dataLayer.push(arguments);}
  gtag('js', new Date());

  gtag('config', 'UA-xxxxxxxxx-x');
</script>


    <meta name="description" content="一、K-means介绍
K-means算法，也称为K-平均或者K-均值，是一种无监督的聚类算法。对于给定的样本集，按照样本之间的距离大小，将样本划分为K个簇，让簇内的点尽量紧密的连接在一起，而让簇间的距离尽量的大。K-means是一种使用广..." />
    <meta name="keywords" content="无监督学习,聚类,k-means,人工智能,机器学习" />
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.10.0/katex.min.css">
    <script src="https://cdn.bootcss.com/highlight.js/9.12.0/highlight.min.js"></script>
  </head>
  <body>
    <div class="main">
      <div class="main-content">
        <div class="site-header">
  <a href="https://JIANG-HS.github.io">
  <img class="avatar" src="https://JIANG-HS.github.io/images/avatar.png?v=1600693149942" alt="">
  </a>
  <h1 class="site-title">
    JIANG-HS
  </h1>
  <p class="site-description">
    姜还是老的辣
  </p>
  <div class="menu-container">
    
      
        <a href="/" class="menu">
          首页
        </a>
      
    
      
        <a href="/archives" class="menu">
          归档
        </a>
      
    
      
        <a href="/tags" class="menu">
          标签
        </a>
      
    
      
        <a href="/post/about" class="menu">
          关于
        </a>
      
    
  </div>
  <div class="social-container">
    
      
    
      
    
      
    
      
    
      
    
  </div>
</div>

        <div class="post-detail">
          <article class="post">
            <h2 class="post-title">
              K-means算法
            </h2>
            <div class="post-info">
              <span>
                2020-07-17
              </span>
              <span>
                7 min read
              </span>
              
                <a href="https://JIANG-HS.github.io/tag/JwXrvo2Mp/" class="post-tag">
                  # 无监督学习
                </a>
              
                <a href="https://JIANG-HS.github.io/tag/MtgqKZxehC/" class="post-tag">
                  # 聚类
                </a>
              
                <a href="https://JIANG-HS.github.io/tag/sDnUkshyy/" class="post-tag">
                  # k-means
                </a>
              
                <a href="https://JIANG-HS.github.io/tag/hPqZti1l1/" class="post-tag">
                  # 人工智能
                </a>
              
                <a href="https://JIANG-HS.github.io/tag/2ypiqV3K8b/" class="post-tag">
                  # 机器学习
                </a>
              
            </div>
            
            <div class="post-content-wrapper">
              <div class="post-content">
                <h1 id="一-k-means介绍">一、K-means介绍</h1>
<p>K-means算法，也称为K-平均或者K-均值，是一种无监督的聚类算法。对于给定的样本集，按照样本之间的距离大小，将样本划分为K个簇，让簇内的点尽量紧密的连接在一起，而让簇间的距离尽量的大。K-means是一种使用广泛的最基础的聚类算法，通常作为学习聚类算法时的第一个算法。<br>
其他的聚类算法还有：K-medoids、k-modes、Clara、Clarans等</p>
<p><strong>聚类</strong>：物理或抽象对象的集合分成由类似的对象组成的多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其他簇中的对象相异。</p>
<p><strong>簇</strong>：本算法中可以理解为，把数据集聚类成k类，即k个簇。</p>
<p><strong>质心</strong>：指各个类别的中心位置，即簇中心。</p>
<p><strong>距离公式</strong>：常用的有：欧几里得距离（欧氏距离）、曼哈顿距离、闵可夫斯基距离等。</p>
<h1 id="二-算法步骤">二、算法步骤</h1>
<h2 id="1文字说明">1.文字说明</h2>
<p>①.给定一个待处理的数据集；<br>
②.记K个簇的中心分别为c<sub>1</sub>,c<sub>2</sub>,...,c<sub>k</sub>;每个簇的样本数量为N<sub>1</sub>,N<sub>2</sub>,...,N<sub>3</sub>;<br>
③.通过欧几里得距离公式计算各点到各质心的距离，把每个点划分给与其距离最近的质心，从而初步把数据集分为了K类；<br>
④.更新质心：通过下面的公式来更新每个质心。就是，新的质心的值等于当前该质心所属簇的所有点的平均值。</p>
<p class='katex-block'><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>c</mi><mi>j</mi></msub><mo>=</mo><mfrac><mn>1</mn><msub><mi>N</mi><mi>j</mi></msub></mfrac><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>j</mi></msub></munderover><msub><mi>x</mi><mi>i</mi></msub><mo separator="true">,</mo><msub><mi>y</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">c_{j}=\frac{1}{N_{j}}\sum_{i=1}^{N_{j}}x_{i},y_{i}
</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.716668em;vertical-align:-0.286108em;"></span><span class="mord"><span class="mord mathdefault">c</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.311664em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight" style="margin-right:0.05724em;">j</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.286108em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:3.2143250000000005em;vertical-align:-1.277669em;"></span><span class="mord"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:1.32144em;"><span style="top:-2.314em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord"><span class="mord mathdefault" style="margin-right:0.10903em;">N</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.311664em;"><span style="top:-2.5500000000000003em;margin-left:-0.10903em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight" style="margin-right:0.05724em;">j</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.286108em;"><span></span></span></span></span></span></span></span></span><span style="top:-3.23em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line" style="border-bottom-width:0.04em;"></span></span><span style="top:-3.677em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">1</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.972108em;"><span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mop op-limits"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:1.9366560000000004em;"><span style="top:-1.872331em;margin-left:0em;"><span class="pstrut" style="height:3.05em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight">i</span><span class="mrel mtight">=</span><span class="mord mtight">1</span></span></span></span><span style="top:-3.050005em;"><span class="pstrut" style="height:3.05em;"></span><span><span class="mop op-symbol large-op">∑</span></span></span><span style="top:-4.4083250000000005em;margin-left:0em;"><span class="pstrut" style="height:3.05em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight"><span class="mord mathdefault mtight" style="margin-right:0.10903em;">N</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3280857142857143em;"><span style="top:-2.357em;margin-left:-0.10903em;margin-right:0.07142857142857144em;"><span class="pstrut" style="height:2.5em;"></span><span class="sizing reset-size3 size1 mtight"><span class="mord mtight"><span class="mord mathdefault mtight" style="margin-right:0.05724em;">j</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.2818857142857143em;"><span></span></span></span></span></span></span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:1.277669em;"><span></span></span></span></span></span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord"><span class="mord mathdefault">x</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.31166399999999994em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight">i</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord"><span class="mord mathdefault" style="margin-right:0.03588em;">y</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.31166399999999994em;"><span style="top:-2.5500000000000003em;margin-left:-0.03588em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight">i</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span></span></p>
<p>⑤.重复步骤3和步骤4，直到质心基本不再变化或者达到最大迭代次数。</p>
<h2 id="2伪代码">2.伪代码</h2>
<pre><code>1：导入或创建训练集，设定K值
2：随机选取K个点作为初始质心（在数据集的范围内）
3：repeat
4：    for i=1,2,...,m(m为样本个数）do
5：        计算K个质心到所有样本的欧式距离
6：        把样本中的点划分给距离最近的质心
7:     end for
8：    for i=1,2,..,k do
9：        求每一个簇的数据的平均值
10：       将求出的平均值赋值给各质心
11:    end for
12：until 当前质心基本不变或者达到最大迭代次数
</code></pre>
<h1 id="三-图形展示">三、图形展示</h1>
<p>假设K=2，即有两个簇，绿色为最初的样本数据集（图a），红色标记和蓝色标记分别为两个质心（图b）。通过计算样本到红色质心和蓝色质心的距离，实现对样本的分类，然后再不断地更新质心的位置，最终得到了一个比较理想的聚类结果（图f）。<br>
<img src="https://JIANG-HS.github.io/post-images/1591347084111.png" alt="" loading="lazy"><br>
顺序为：a→b→c→d→e→f<br>
可以看到，整个算法是一个不断更新质心和簇的过程。</p>
<h1 id="四-代码实现">四、代码实现</h1>
<pre><code>import matplotlib.pyplot as plt
from random import uniform
from math import sqrt

#创建一个数据集。
#注意：本方法创建的数据集每次运行结果都不相同
m = 60 #数据个数
data = [[],[]] #[[存储x轴数据],[存储y轴数据]]
for i in range(m):
    if i &lt; m/3: 
        data[0].append(uniform(1,5))#随机设定
        data[1].append(uniform(1,5))
    elif i &lt; 2*m/3:
        data[0].append(uniform(6,10))
        data[1].append(uniform(1,5))
    else:
        data[0].append(uniform(3,8))
        data[1].append(uniform(5,10))
#将创建的数据集画成散点图
plt.scatter(data[0],data[1])
plt.xlim(0,11)
plt.ylim(0,11)
plt.show()

#定义欧几里得距离
def distEuclid(x1,y1,x2,y2):
    d = sqrt((x1-x2)**2+(y1-y2)**2)
    return d

cent0 = [uniform(2,9),uniform(2,9)] #定义K=3个质心,随机赋值
cent1 = [uniform(2,9),uniform(2,9)] #[x,y]
cent2 = [uniform(2,9),uniform(2,9)]
mark = [] #标记列表
dist = [[],[],[]]#各质心到所有点的距离列表
#核心
for n in range(50):
    #计算各质心到所有点的距离
    for i in range(m):
        dist[0].append(distEuclid(cent0[0],cent0[1],data[0][i],data[1][i]))
        dist[1].append(distEuclid(cent1[0],cent1[1],data[0][i],data[1][i]))
        dist[2].append(distEuclid(cent2[0],cent2[1],data[0][i],data[1][i]))
    #对数据进行整理
    sum0_x = sum0_y = sum1_x = sum1_y = sum2_x = sum2_y = 0
    number0 = number1 = number2 = 0
    for i in range(m):
        if dist[0][i]&lt;dist[1][i] and dist[0][i]&lt;dist[2][i]:
            mark.append(0)
            sum0_x += data[0][i]
            sum0_y += data[1][i]
            number0 += 1
        elif dist[1][i]&lt;dist[0][i] and dist[1][i]&lt;dist[2][i]:
            mark.append(1)
            sum1_x += data[0][i]
            sum1_y += data[1][i]
            number1 += 1
        elif dist[2][i]&lt;dist[0][i] and dist[2][i]&lt;dist[1][i]:
            mark.append(2)
            sum2_x += data[0][i]
            sum2_y += data[1][i]
            number2 += 1    
    #更新质心
    cent0 = [sum0_x/number0,sum0_y/number0]
    cent1 = [sum1_x/number1,sum1_y/number1]
    cent2 = [sum2_x/number2,sum2_y/number2]

#画图
for i in range(m):
    if mark[i] == 0:
        plt.scatter(data[0][i],data[1][i],color='red')
    if mark[i] == 1:
        plt.scatter(data[0][i],data[1][i],color='blue')
    if mark[i] == 2:
        plt.scatter(data[0][i],data[1][i],color='green')     
plt.scatter(cent0[0],cent0[1],marker='*',color='red')
plt.scatter(cent1[0],cent1[1],marker='*',color='blue')
plt.scatter(cent2[0],cent2[1],marker='*',color='green')
plt.xlim(0,11)
plt.ylim(0,11)
plt.show()
</code></pre>
<p>几种分类较好的结果：<br>
<img src="https://JIANG-HS.github.io/post-images/1594985394419.png" alt="alt" loading="lazy"><br>
<img src="https://JIANG-HS.github.io/post-images/1594985645192.png" alt="" loading="lazy"><br>
分类较差的结果：<br>
<img src="https://JIANG-HS.github.io/post-images/1594985625937.png" alt="" loading="lazy"><br>
<img src="https://JIANG-HS.github.io/post-images/1594991121899.png" alt="" loading="lazy"></p>
<h1 id="五-k-means-算法存在的问题">五、K-means 算法存在的问题</h1>
<p>由于K-means算法简单且易于实现，因此K-means算法得到了很多的应用，但是从K-means算法的过程中可以发现两个问题：<br>
1.簇中心的个数K是需要事先给定的，对事先比较了解的数据集可以很好地进行分类，但在处理未知数据时无法确定K的值为多少时更合适，就无从下手或者只能盲目尝试。<br>
2.K-means算法在聚类之前，需要随机初始化K个质心，如果质心选择不好，如上面的图形所示，最后的聚类结果可能会比较差。</p>

              </div>
              <div class="toc-container">
                <ul class="markdownIt-TOC">
<li><a href="#%E4%B8%80-k-means%E4%BB%8B%E7%BB%8D">一、K-means介绍</a></li>
<li><a href="#%E4%BA%8C-%E7%AE%97%E6%B3%95%E6%AD%A5%E9%AA%A4">二、算法步骤</a>
<ul>
<li><a href="#1%E6%96%87%E5%AD%97%E8%AF%B4%E6%98%8E">1.文字说明</a></li>
<li><a href="#2%E4%BC%AA%E4%BB%A3%E7%A0%81">2.伪代码</a></li>
</ul>
</li>
<li><a href="#%E4%B8%89-%E5%9B%BE%E5%BD%A2%E5%B1%95%E7%A4%BA">三、图形展示</a></li>
<li><a href="#%E5%9B%9B-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0">四、代码实现</a></li>
<li><a href="#%E4%BA%94-k-means-%E7%AE%97%E6%B3%95%E5%AD%98%E5%9C%A8%E7%9A%84%E9%97%AE%E9%A2%98">五、K-means 算法存在的问题</a></li>
</ul>

              </div>
            </div>
          </article>
        </div>

        
          <div class="next-post">
            <div class="next">下一篇</div>
            <a href="https://JIANG-HS.github.io/post/6TmSsQzOC/">
              <h3 class="post-title">
                KNN算法实现鸢尾花数据集的分类
              </h3>
            </a>
          </div>
        

        
          
            <link rel="stylesheet" href="https://unpkg.com/gitalk/dist/gitalk.css">
<script src="https://unpkg.com/gitalk/dist/gitalk.min.js"></script>

<div id="gitalk-container"></div>

<script>

  var gitalk = new Gitalk({
    clientID: '',
    clientSecret: '',
    repo: '',
    owner: '',
    admin: [''],
    id: (location.pathname).substring(0, 49),      // Ensure uniqueness and length less than 50
    distractionFreeMode: false  // Facebook-like distraction free mode
  })

  gitalk.render('gitalk-container')

</script>

          

          
        

        <div class="site-footer">
  Powered by <a href="https://github.com/getgridea/gridea" target="_blank">Gridea</a>
  <a class="rss" href="https://JIANG-HS.github.io/atom.xml" target="_blank">
    <i class="ri-rss-line"></i> RSS
  </a>
</div>

      </div>
    </div>

    <script>
      hljs.initHighlightingOnLoad()

      let mainNavLinks = document.querySelectorAll(".markdownIt-TOC a");

      // This should probably be throttled.
      // Especially because it triggers during smooth scrolling.
      // https://lodash.com/docs/4.17.10#throttle
      // You could do like...
      // window.addEventListener("scroll", () => {
      //    _.throttle(doThatStuff, 100);
      // });
      // Only not doing it here to keep this Pen dependency-free.

      window.addEventListener("scroll", event => {
        let fromTop = window.scrollY;

        mainNavLinks.forEach((link, index) => {
          let section = document.getElementById(decodeURI(link.hash).substring(1));
          let nextSection = null
          if (mainNavLinks[index + 1]) {
            nextSection = document.getElementById(decodeURI(mainNavLinks[index + 1].hash).substring(1));
          }
          if (section.offsetTop <= fromTop) {
            if (nextSection) {
              if (nextSection.offsetTop > fromTop) {
                link.classList.add("current");
              } else {
                link.classList.remove("current");    
              }
            } else {
              link.classList.add("current");
            }
          } else {
            link.classList.remove("current");
          }
        });
      });

    </script>
  </body>
</html>
